#include <stdio.h>
#include <stdlib.h>

int n;

/*
 https://www.cnblogs.com/chengxiao/p/6104371.html
 * 希尔排序
   间隔增量 插入排序 
 希尔排序也是插入排序的一种，但它在效率上要比上面的直接插入排序高，
 它是对直接插入排序的改进，它的基本思想是先取一个小于n的整数d1作为第一个增量，
 把文件的全部记录分组。
 所有距离为d1的倍数的记录放在同一个组中。
 先在各组内进行直接插入排序；
 然后，取第二个增量d2< d1重复上述的分组和排序，
 直至所取的增量dt=1(dt<…< d2< d1)，即所有记录放在同一组中进行直接插入排序为止，
 增量序列尤为关键，一般的初次取序列的一半为增量，以后每次减半，直到增量为1

// 希尔排序  之间插入排序的 改进版本
// 	希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；
// 随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
// 简单插入排序很循规蹈矩  希尔排序在数组中采用跳跃式分组的策略
// 在此我们选择增量gap=length/2 分组数，缩小增量继续以gap = gap/2的方式，这
// 种增量选择我们可以用一个序列来表示，{n/2,(n/2)/2, ..., 1}，称为增量序列。

//  例如  [8 9 1 7 2 3 5 4 6 0 10]个元素 第一次 分成 10/2 = 5组
// 第0位置上 和第 0+5 位置上，1和6位置上...
// 即 元素 [8 3][9 5] [1 4] [7 6] [2 0]分别为一组
// 对每组分别进行 直接插入排序
// 得到  [3 8] [5 9] [1 4] [6 7] [0 2]
// 原数组为 [3 5 1 6 0 8 9 4 7 2]  再分成 5/2 = 2 组进行排序

// 即 [3 1 0 9 7] [5 6 8 4 2] 两组 再分别进行直接排序
// 得到 [0 1 3 7 9] [2 4 5 6 8]
// 原数组 [0 2 1 4 3 5 7 6 9 8] 在分为 2/2 =1 组进行直接排序
 
 // 经过上面的 宏观调控 整个数组 的有序化程度 喜人
 // 此时，仅仅需要对以上 数列简单 微调
 // [0 1 2 3 4 5 6 7 8 9]

 */
void ShellSort(int *array)
{
    int k = n / 2; //增量序列（仅作举例）  10/2=5
    while (k > 0)
    {
        int i, j;
        for (i = k + 1; i <=n; i++)// 6~10
        {
            if (array[i] < array[i - k])// 原先的直接排序是一次取后面的一个元素 这里是 间隔一个增量 
            {
                array[0] = array[i];// 1   1+k，2 2+k  保存取出来的元素 小 
                for (j = i - k; j > 0 && array[0] < array[j]; j -= k)
                {
                    array[j + k] = array[j];//大的移到后面 
                }
                array[j + k] = array[0];
            }
        }
        k = k / 2;//增量减小 
    }
}

void ShellSort2(int *a, int s)
{
 // 1】 遍历每一次 分组  int gap = data.size()/2; gap > 0; gap/=2 每一次 分组数为 gap
    for (int gap = s/2; gap > 0; gap/=2)
    {
     // 2】 遍历 每一个 间隔分组数组  从第gap个元素，逐个对其所在组进行直接插入排序操作 
        for (int i = gap ; i <=s; ++i)// 6~10
          {         
            int j;
            int temp = a[i];// 每个分组的首个 元素
            // 3】对每一个分组数组 从后向前（间隔gap） 遍历其有序数组
            for(j = i-gap; j>=0; j -= gap){
                if(a[j] > temp)  a[j+gap] = a[j];// 4】 有序数组内 大于 temp的元素依次后移间隔gap（）
                else break;// 5】 找到 比temp 小的元素 a[j]
             }
            a[j+gap] = temp;// 6】将temp 放入 a[j]的后一个元素(间隔gap) a[j + gap]
          }
    }
}



int main()
{
    int i;
    int *array;
    printf("请输入数组的大小：");
    scanf("%d", &n);
    array = (int*) malloc(sizeof(int) * (n + 1));
    printf("请输入数据（用空格分隔）：");
    for (i = 1; i <= n; i++)
    {
        scanf("%d", &array[i]);
    }
    ShellSort(array);
    printf("排序后为：");
    for (i = 1; i <= n; i++)
    {
        printf("%d ", array[i]);
    }
    printf("\n");
}
